package cn.lbd.datastructure;


public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        HeroThreadedTreeNode root = new HeroThreadedTreeNode(1, "宋江");
        HeroThreadedTreeNode heroThreadedTreeNode3 = new HeroThreadedTreeNode(3, "吴用");
        HeroThreadedTreeNode heroThreadedTreeNode6 = new HeroThreadedTreeNode(6, "林冲");
        HeroThreadedTreeNode heroThreadedTreeNode8 = new HeroThreadedTreeNode(8, "呼延灼");
        HeroThreadedTreeNode heroThreadedTreeNode10 = new HeroThreadedTreeNode(10, "柴进");
        HeroThreadedTreeNode heroThreadedTreeNode14 = new HeroThreadedTreeNode(14, "武松");

        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);

        root.setLeft(heroThreadedTreeNode3);
        root.setRight(heroThreadedTreeNode6);
        heroThreadedTreeNode3.setLeft(heroThreadedTreeNode8);
        heroThreadedTreeNode3.setRight(heroThreadedTreeNode10);
        heroThreadedTreeNode6.setLeft(heroThreadedTreeNode14);

        threadedBinaryTree.preOrder();
        System.out.println();
        /*threadedBinaryTree.infixOrder();
        System.out.println();
        threadedBinaryTree.postOrder();
        System.out.println();*/

        //中序线索化
        threadedBinaryTree.infixThreadedNodes();
        System.out.println("10号的前驱节点" + heroThreadedTreeNode10.getLeft());
        System.out.println("10号的后继节点" + heroThreadedTreeNode10.getRight());
        //中序遍历线索化二叉树
        threadedBinaryTree.infixThreadedNodesList();
        /*threadedBinaryTree.preThreadedNodes();
        System.out.println("10号的前驱节点"+heroThreadedTreeNode10.getLeft());
        System.out.println("10号的后继节点"+heroThreadedTreeNode10.getRight());*/
    }
}

/**
 * 线索二叉树
 * 左右节点指向有可能是子树，也有可能是前驱后继节点
 **/
class ThreadedBinaryTree {
    private HeroThreadedTreeNode root;
    //因为目前树是单向，为了线索化，需要创建一个指向当前节点前驱节点的指针pre，pre总是保留前一个节点
    private HeroThreadedTreeNode pre = null;

    public void setRoot(HeroThreadedTreeNode root) {
        this.root = root;
    }

    //中序线索化遍历
    /*HeroThreadedTreeNode node = root;
        while (node != null) {
        while (node.getLeftType() == 0) {
            node = node.getLeft();
        }
        System.out.println(node);
        while (node.getRightType() == 1) {
            node = node.getRight();
            System.out.println(node);
        }
        node = node.getRight();
    }*/
    public void infixThreadedNodesList() {
        System.out.println("中序遍历开始");
        HeroThreadedTreeNode node = root;
        while (node != null){
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            System.out.println(node);
            while (node.getRightType()==1){
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();
        }

    }

    //前序线索化遍历
    public void preThreadedNodesList() {

    }

    //后序线索化遍历
    public void postThreadedNodesList() {

    }

    //前序线索化
    public void preThreadedNodes() {
        preThreadedNodes(root);
    }

    //前序线索化
    public void preThreadedNodes(HeroThreadedTreeNode node) {

    }

    //中序线索化
    public void infixThreadedNodes() {
        infixThreadedNodes(root);
    }


    //中序线索化
    public void infixThreadedNodes(HeroThreadedTreeNode node) {
        //二叉树为空，不能线索化
        if (node == null) {
            return;
        }
        //递归的线索化左子树
        infixThreadedNodes(node.getLeft());
        //线索化当前节点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        //每处理一个节点后，让当前节点是下一个结点的前驱节点
        pre = node;
        //递归的线索化右子树
        infixThreadedNodes(node.getRight());
    }

    //后序线索二叉树
    public void postThreadedNodes() {
        postThreadedNodes(root);
    }

    //后序线索二叉树
    public void postThreadedNodes(HeroThreadedTreeNode node) {

    }

    //前序
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

    //中序
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

    //后序
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

}


class HeroThreadedTreeNode {
    private int no;
    private String name;
    private HeroThreadedTreeNode left;
    private HeroThreadedTreeNode right;
    //0：左子树   1：前驱
    private int leftType;
    //0：右子树   1：后继
    private int rightType;

    public HeroThreadedTreeNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public HeroThreadedTreeNode getLeft() {
        return left;
    }

    public void setLeft(HeroThreadedTreeNode left) {
        this.left = left;
    }

    public HeroThreadedTreeNode getRight() {
        return right;
    }

    public void setRight(HeroThreadedTreeNode right) {
        this.right = right;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "HeroThreadedTreeNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //后序
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

}